4752. Кинотеатр

Однажды, ученики B-й школы города G решили съездить в кино. Администрация кинотеатра расположила их в зале размера n × m, который специально был подобран так, чтобы все места были заняты школьниками. Каждому посетителю кинотеатра был выдан свой номер.

Школьники заняли свои места следующим образом: они входили в зал в порядке, в котором шли их номера, и полностью занимали сначала первый ряд, потом второй, потом третий и т.д.

Однако классный руководитель решил, что такая рассадка плохо влияет на поведение учащихся и пересадил их по-другому: ученики сначала занимали все первые места каждого ряда, потом все вторые места каждого ряда и т.д. (см. рисунок).

Администрация решила выяснить, сколько учащихся не поменяют своего места после пересадки.

Вход. В первой строке заданы числа n и m (1 ≤ n, m ≤ 1000).

Выход. Выведите одно число – количество учеников, которые в результате пересадки остануться сидеть на тех же местах.

Пример входа 1	Пример выхода 1
3 4	2
Пример входа 2	Пример выхода 2
3 3	3

РЕШЕНИЕ

массив

Анализ алгоритма

Заполним два двумерных массива как сказано в условии задачи (0 ≤ i < n, 0 ≤ j < m):

· массив c1 заполним как сели школьники: c1[i][j] = i * m + j + 1;

· массив c2 заполним как пересадил школьников классный руководитель: c2[i][j] = j * n + i + 1;

Количество пар (i, j), для которых c1[i][j] = c2[i][j], равно числу учащихся, которые не поменяют своего места после пересадки.

Реализация алгоритма

Объявим двумерные массивы c1 и c2.

#define MAX 1010

int c1[MAX][MAX], c2[MAX][MAX];

Читаем входные данные.

scanf("%d %d",&n,&m);

Заполняем массив c1 по строкам и массив c2 по рядам.

for (i = 0; i < n; i++)

for (j = 0; j < m; j++)

{

c1[i][j] = i * m + j + 1;

c2[i][j] = j * n + i + 1;

}

В переменной res вычисляем количество пар (i, j), для которых c1[i][j] = c2[i][j].

res = 0;

for (i = 0; i < n; i++)

for (j = 0; j < m; j++)

if (c1[i][j] == c2[i][j]) res++;

Выводим ответ.

printf("%d\n",res);

Java реализация

import java.util.*;

public class Main

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int n = con.nextInt();

int m = con.nextInt();

int i, j;

int c1[][] = new int[n][m];

int c2[][] = new int[n][m];

for (i = 0; i < n; i++)

for (j = 0; j < m; j++)

{

c1[i][j] = i * m + j + 1;

c2[i][j] = j * n + i + 1;

}

int res = 0;

for (i = 0; i < n; i++)

for (j = 0; j < m; j++)

if (c1[i][j] == c2[i][j]) res++;

System.out.println(res);

con.close();

}

}

Python реализация

n, m = map(int,input().split())

c1 = [[0 for j in range(m)] for i in range(n)]

c2 = [[0 for j in range(m)] for i in range(n)]

for i in range(n):

for j in range(m):

c1[i][j] = i * m + j + 1

c2[i][j] = j * n + i + 1

res = 0;

for i in range(n):

for j in range(m):

if c1[i][j] == c2[i][j]: res += 1

print(res)